#ifndef COIN_H_
#define COIN_H_

#include<vector>

/** 
 * pair中的含义: first为每个硬币的金额; second为每个硬币的个数
 * amount: 总金额
 */
int min_tot_num(std::vector<std::pair<int, int>> &coins, int amount){
    int coin_kinds = coins.size();

    /* 创建二维dp数组, `-1`标志着正无穷(即解法不存在) */
    std::vector<std::vector<int> > dp(coin_kinds+1, std::vector<int>(amount+1, -1));
    dp[coin_kinds][0] = 0;  /* 边界条件 */
    
    for(int i = coin_kinds-1; i >= 0; i--){
        for(int j = 0; j <= amount; j++){
            for(int k = 0; k <= coins[i].second && coins[i].first * k <= j; k++){
                int tmp = dp[i+1][j-coins[i].first * k];
                if(tmp == -1)
                    continue;   // 若为`正无穷`, 则不必更新
                if(dp[i][j] == -1)
                    dp[i][j] = tmp + k; // 若当前为`正无穷`, 则直接更新为tmp值
                else    
                    dp[i][j] = std::min(dp[i][j], tmp + k); // 否则让tmp与当前值比较
            }
        }
    }

    return dp[0][amount];   // 最终更新的行, 即为最终的dp结果
}

#endif